package com.example.java.yugutou.chapter1_linklist.level2.topic2_2回文序列;

import java.util.Stack;

/**
 * @Author : 佩萁
 * Description :判断链表是不是回文序列
 * @Create : 2023/12/12 - 10:27
 */
public class IsPalindromic {
    public static void main(String[] args) {
//        int[] a = {1, 2, 3, 4, 4, 3, 2, 1};
        int [] a = {1,2,3,2,1};
        ListNode node = initLinkedList(a);
        int testMethod = 3;
        boolean result = false;
        switch (testMethod) {
            case 1:
                result = isPaLindromByAllStack(node);
                break;
            case 2:
                result = isPaLindromeByHalfStack(node);
                break;
            case 3:
                result = isPalindromeByTwoPoints(node);
                break;
        }
        System.out.println("result:" + result);
    }

    /**
     * 方法1：全部压栈
     */
    public static boolean isPaLindromByAllStack(ListNode head) {
        ListNode temp = head;//获取头结点地址
        //创建栈
        Stack<Integer> stack = new Stack<>();
        //如果头结点不为空，我们就对其进行压栈
        while (temp != null) {
            stack.push(temp.val);//将结点值压入栈
            //指针向后遍历移动一位，直到移动到最后一位，然后再次进行while循环为空跳出
            temp = temp.next;
        }
        //出栈
        while (head != null) {
            //从头从尾比较
            if (head.val != stack.pop()) {
                return false;//如果不相等直接跳出
            }
            head = head.next;
        }
        //如果循环都未被打断跳出，说明这个链表是回文序列，返回true
        return true;
    }

    /**
     * 方法2：先全部压栈然后只比较一半的元素，也就是只有一半的元素出栈，链表也只遍历一半
     */
    public static boolean isPaLindromeByHalfStack(ListNode head) {
        //先判断链表是否为空，为空直接返回true，算是一种特殊的回文序列
        if (head == null) {
            return true;
        }
        //初始化一个节点接收头结点
        ListNode temp = head;
        //创建一个栈
        Stack<Integer> stack = new Stack<>();
        //定义一个变量，表示链表长度
        int len = 0;
        //进行压栈
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
            len++;//记录链表长度
        }
        //链表长度缩短一半，这里只是将变量减小一半而已
        len >>= 1;
        //每出栈一个元素比较,len--，当len<0,之前循环都未终止，说明这是个回文序列
        while (len-- >= 0) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 方法3：通过双指针的方式来判断
     */
    public static boolean isPalindromeByTwoPoints(ListNode head) {
        //如果链表只有一个头结点或者链表为空
        if (head == null || head.next == null) {
            return true;
        }
        //一个快指针，一个慢指针  快指针移动速度是慢指针的2倍
        //当快指针到链尾，慢指针到链表中间
        ListNode slow = head, fast = head;
        //pre是前半部分链表的辅助指针，用于在反转链表时修改结点的next指针
        //prepare是pre的前一个结点，用于在链表反转时帮助调整pre的指向，最初初始化为null
        ListNode pre = head, prepare = null;
        //这些指针协同工作，通过快慢指针找到中点，找到中点后，反转前半部分链表。然后
        //比较前半部分和后半部分是否一样，以确定链表是否是回文的
        while (fast != null && fast.next != null) {//这个判断说明快指针还没有走到链表尾
            pre = slow;//辅助指针跟着慢指针不断后移

            slow = slow.next;
            fast = fast.next.next;
            //在移动的过程中对前半部分链表进行反转
            //动图演示
            //https://www.bilibili.com/video/BV1Uw411m7t3/?vd_source=cf2ac0d09b7ffd99dd2c5a37cf1ea2f4
            pre.next = prepare;
            prepare = pre;
        }
        if (fast != null) {
            slow = slow.next;
        }
        while (pre != null && slow != null) {
            //如果链表后半段和前半段反转后的有不等的地方，说明链表不是回文
            if (pre.val != slow.val) {
                return false;
            }
            pre = pre.next;//反转后的链表
            slow = slow.next;//这里slow已经在链表后半段移动了
        }
        return true;
    }

    //节点类
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int x) {
            val = x;
            next = null;
        }
    }

    //初始化链表
    //传入数组，将数组初始化为链表
    private static ListNode initLinkedList(int[] array) {
        ListNode head = null, cur = null;
        for (int i = 0; i < array.length; i++) {
            //循环遍历数组，将数组元素作为节点val
            ListNode newNode = new ListNode(array[i]);
            //创建的第一个节点下一个结点为null
            newNode.next = null;
            if (i == 0) {//我们需要先确定头结点
                head = newNode;
                //当前指针指向head
                cur = head;
            } else {
                //如果结点不是头结点，当前指针就应该指向新结点
                cur.next = newNode;
                cur = newNode;
            }
        }
        return head;//返回头指针
    }
}
